\section{Appendix~\ref{app:s:l:3agents}: The Proof of Lemma~\ref{l:3agents}}
\label{app:s:l:3agents}

We start with some useful technical observations about the preferred agents and the thresholds of the leftmost and the rightmost locations. The following proposition is an immediate consequence of Lemma~\ref{l:i-cases} and Corollary~\ref{cor:dict-location}.

\begin{proposition}\label{prop:dict-location-a}
If there is an $(i|j,k)$-well-separated instance $\vec{x}$, such that $F_2(\vec{x}) = x_j$, then $\l(i, x_i) = (j, x_i)$. If there is an $(i,j|k)$-well-separated instance $\vec{x}$, such that $F_1(\vec{x}) = x_j$, then $\r(k, x_k) = (j, x_k)$.
\end{proposition}

The following lemma shows that the preferred agent and the threshold of an agent can only depend on her identity, and not on her location.

\begin{lemma}\label{l:always-a}
Let $i$ be an agent and $a$ be a location such that $\l(i, a) = (j, a)$ (resp. $\r(i, a) = (j, a)$). Then, for all locations $b \in \reals$, $\l(i, b) = (j, b)$ (resp. $\r(i, b) = (j, b)$).
\end{lemma}

\begin{proof}
We only show that if $\l(i, a) = (j, a)$, then $\l(i, b) = (j, b)$, for all locations $b$. The claim that $\r(i, a) = (j, a)$ implies that $\r(i, b) = (j, b)$, for all locations $b$, follows from a symmetric argument.
%
Let $i$ be an agent and $a$ be a location such that $\l(i, a) = (j, a)$, for some agent $j$, and let $b$ be any location. To show that $\l(i, b) = (j, b)$, we consider two appropriate instances $\vec{x}$ and $\vec{y}$.

The instance $\vec{x}$ is defined as $x_i = a$, $x_j = a + 1$, and $x_k = r > \max\{a+1, b\}$, where $r$ is chosen large enough that $\vec{x}$ is an $(i,j|k)$-well-separated instance. Since $x_j \geq \l_p(i, a)$,  Lemma~\ref{l:non-separated} implies that $x_j \in F(\vec{x})$. Then, since $\vec{x}$ is an $(i,j|k)$-well-separated instance, by Proposition~\ref{prop:dict-location-a}, $\r(k, r) = (j, r)$.

The instance $\vec{y}$ is defined as $y_i = b$, $y_j = r-\eps$, and $y_k = r$, where $\eps > 0$ is chosen so small that $\vec{y}$ is an $(i|j,k)$-well-separated instance. Since $y_j \leq \r(k, r)$, the symmetric version of Lemma~\ref{l:non-separated} applied to $\vec{y}$ implies that $y_j \in F(\vec{y})$. Then, since the instance $\vec{y}$ is $(i|j,k)$-well-separated, by Proposition~\ref{prop:dict-location-a},
$\l(i, b) = (j, b)$.
\qed\end{proof}


The next lemma shows that if an agent $i$ imposes another agent $j$ as a partial dictator, the third agent $k$ agrees with $i$ not only on the existence of a partial dictator, but also on the partial dictator's identity.

\begin{lemma}\label{l:others-a}
If there exists an agent $i$ and a location $a$ such that $\l(i, a) = (j, a)$ (resp. $\r(i, a) = (j, a)$), then for the third agent $k$ and all locations $b \in \reals$, $\r(k, b) = (j, b)$ (resp. $\l(k, b) = (j, b)$).
\end{lemma}

\begin{proof}
We only consider the case where $\l(i, a) = (j, a)$, and show that $\r(k, b) = (j, b)$, for the third agent $k$ and all locations $b$. The symmetric case follows from a symmetric argument.
%
Let $i$ be an agent and $a$ be a location such that $\l(i, a) = (j, a)$, for some agent $j$, and let $b$ be any location of the third agent $k$. Without loss of generality, we assume that $a < b$. Otherwise, we select a location $a'$ of $i$ with $a' < b$, and have that $\l(i, a') = (j, a')$, by Lemma~\ref{l:always-a}. To establish the lemma, we consider an instance $\vec{x}$ defined as $x_i = a$, $x_k = b$, and $x_j = a+\eps$, where $\eps > 0$ is chosen small enough that $\vec{x}$ is an $(i,j|k)$-well-separated instance. Since $x_j \geq \l_p(i, a)$, Lemma~\ref{l:non-separated} implies that $x_j \in F(\vec{x})$. Then, since $\vec{x}$ is an $(i,j|k)$-well-separated instance, by Proposition~\ref{prop:dict-location-a}, $\r(k, b) = (j, b)$.
\qed\end{proof}


The following lemma shows that if there is an agent $j$ imposed as a partial dictator by the leftmost and the rightmost agent, $j$ is the only one with this property. Thus, if $j$ is located at the one extreme of the instance, the other facility is placed at the other extreme.

\begin{lemma}\label{l:only-dictator}
If there exists an agent $i$ and a location $a$ such that $\l(i, a) = (j, a)$, then for all locations $b \in \reals$, $\l_p(j, b) =\,\uparrow$ and $\r(j, b) =\,\downarrow$.
\end{lemma}

\begin{proof}
We only show that for all locations $b$, $\l(j, b) =\,\uparrow$. The claim that $\r(j, b) =\,\downarrow$ follows from a symmetric argument.
%
In the following, we let $(i, a)$ be any agent-location pair with $\l_p(i, a) = (j, a)$, and let $k$ be the third agent. We observe that for all locations $a' \in \reals$, $\l(i, a') = (j, a')$, by Lemma~\ref{l:always-a}, and $\r(k, a') = (j, a')$, by Lemma~\ref{l:others-a}.
%
For sake of a contradiction, we assume that for some location $b \in \reals$, $\l_p(j, b) = b$. Therefore, there exists a (unique) preferred agent $\ell \in \{i, k\}$ such that $\l(j, b) = (\ell, b)$, and by Lemma~\ref{l:always-a}, for all locations $b' \in \reals$, $\l(j, b') = (\ell, b')$. Moreover, for all instances $\vec{x}$ with $x_j = b < \min\{ x_i, x_k \}$, Lemma~\ref{l:non-separated} implies that $x_\ell \in F(\vec{x})$. To reach a contradiction, we next show that $\l_\ell(j, b) \neq i$ and that $\l_\ell(j, b) \neq k$.

To this end, we first assume that $\l_\ell(j, b) = i$, and consider an instance $\vec{y}$ with $y_j = 0$, $y_k = 1$, and $y_i = \eps$, where $\eps > 0$ is chosen small enough that $\vec{y}$ is an $(j,i|k)$-well-separated instance.
%
Since $\l(j, 0) = (i, 0)$, since $j$ is the leftmost agent, and since $y_i > 0$, Lemma~\ref{l:non-separated} implies that $y_i \in F(\vec{x})$.
%
Moreover, since $\r(k, 1) = (j, 1)$, $k$ is the rightmost agent, and $y_j < 1$, the symmetric version of Lemma~\ref{l:non-separated} implies that $y_j \in F(\vec{x})$. Therefore, the agent $k$ is served by the facility at $y_i$, which contradicts $F$'s bounded approximation ratio, because the instance $\vec{y}$ is $(j,i|k)$-well-separated. %Consequently, $\l_\ell(j, b) \neq i$.

We have also to consider the case where $\l_\ell(j, b) = k$. In this case, we consider an instance $\vec{z}$ with $z_i = 0$, $z_j = 1$, and $z_k = 1+\eps$, where $\eps > 0$ is chosen small enough that $\vec{z}$ is an $(i|j,k)$-well-separated instance.
%
Since $\l(i, 0) = (j, 0)$, $i$ is the leftmost agent in $\vec{z}$, $z_j > 0$, and the instance $\vec{z}$ is $(i|j,k)$-well-separated, Lemma~\ref{l:i-separated} implies that $F_2(\vec{z}) = z_j$.
%
Therefore, $z_k \not\in F(\vec{z})$, and there is a $z_k$-hole $(l, r)$ in the imageset $I_k(z_i, z_j)$ with $l = 1$. We now consider the instance $\vec{z}' = (\vec{z}_{-\{i,k\}}, r, r-\delta)$, where $\delta > 0$ is chosen small enough that $r-\delta$ is in the right half of the hole $(l, r)$ and $\vec{z}'$ is an $(j|k,i)$-well-separated instance. We observe that $F(\vec{z}') = (r-\delta, r)$.
%
More specifically, $r = z'_i \in F(\vec{z}')$, due to $F$'s strategyproofness. Otherwise, the agent $i$ could switch to location $z_i$ and have $r \in F(\vec{z}'_{-i}, z_i)$, since $r$ is the closest point to $z'_k = r-\delta$ in the imageset $I_k(z_i, z_j)$.
%
Furthermore, since $\l(j, 1) = (k, 1)$, since $j$ is the leftmost agent in $\vec{z}'$, and since $z'_k > 1$, Lemma~\ref{l:non-separated} implies that $r-\delta = z'_k \in F(\vec{z}')$.
%
Therefore, the agent $j$ is served by the facility at $z'_k$, which contradicts $F$'s bounded approximation ratio, because the instance $\vec{z}'$ is $(j|k,i)$-well-separated. %Hence, $\l_\ell(j, b) \neq k$.
\qed\end{proof}


We are now ready to proceed with the proof of Lemma~\ref{l:3agents}. The proof essentially establishes that the behavior of any nice mechanism $F$ is essentially characterized by whether there are two agents that agree on imposing the third agent as a partial dictator or not.


\begin{proof}[of Lemma~\ref{l:3agents}]
We distinguish between the case where for all agents $i \in \{ 1, 2, 3\}$ and for all locations $a \in \reals$, $\l_p(i, a) =\,\uparrow$, and the case where there exists an agent $i \in \{ 1, 2, 3\}$ and a location $a \in \reals$ such that $\l_p(i, a) = a$. Lemma~\ref{l:i-cases} implies that these two cases are indeed complementary to each other.

\smallskip\noindent{\bf Case I: $\forall i \forall a \, \l_p(i, a) =\,\uparrow$.}
%
We show that in this case, $F$ always allocates the facilities to two extremes.
%
To this end, we let $\vec{x}$ be any instance, and let $i$ be the leftmost agent and $k$ be the rightmost agent in $\vec{x}$. By hypothesis, $\l_p(i, x_i) =\,\uparrow$. Therefore, by Lemma~\ref{l:non-separated-inside}, $F_2(\vec{x}) = x_k$.
%
Moreover, $\r_p(k, x_k) =\,\downarrow$, since otherwise, it would be $\r_p(k, x_k) = x_k$, by Lemma~\ref{l:i-cases}, and thus $\l_p(i, x_i) = x_i$, by Lemma~\ref{l:others-a}, which contradicts the hypothesis. Therefore, by the symmetric version of Lemma~\ref{l:non-separated-inside}, $F_1(\vec{x}) = x_i$.


\smallskip\noindent{\bf Case II: $\exists i \exists a \, \l_p(i, a) = a$.}
%
We let $(i, a)$ be any agent-location pair with $\l_p(i, a) = a$, let $j = \l_\ell(i, a)$ be the preferred agent of $i$, and let $k$ be the third agent. Therefore, for all locations $b$, $\l_p(j, b) =\,\uparrow$ and $\r_p(j, b) =\,\downarrow$, by Lemma~\ref{l:only-dictator}. We next show that in this case, the agent $j$ serves as a partial dictator, and satisfies the latter case of the conclusion.

We first observe that for all locations $a' \in \reals$, $\l(i, a') = (j, a')$, by Lemma~\ref{l:always-a}, and $\r(k, a') = (j, a')$, by Lemma~\ref{l:others-a}. Therefore, for all instances $\vec{x}$ with $x_i < x_k$, $x_j \in F(\vec{x})$. More specifically, if $x_i < x_j$, this follows from Lemma~\ref{l:non-separated}, while if $x_j < x_k$, this follows from the symmetric version of Lemma~\ref{l:non-separated}. Then, using Lemma~\ref{l:non-separated-inside}, we obtain the conclusion of the lemma for all instances $\vec{x}$ with $x_i < x_k$\,:

\begin{itemize}
\item For all instances $\vec{x}$ with $x_i < x_j < x_k$, $x_j \in F(\vec{x})$.

\item For all instances $\vec{x}$ with $x_j < x_i < x_k$, $F_1(\vec{x}) = x_j$ and $F_2(\vec{x}) = x_k$, by Lemma~\ref{l:non-separated-inside}, because $\l_p(j, x_j) =\,\uparrow$. Therefore, $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$.

\item For all instances $\vec{x}$ with $x_i < x_k < x_j$, $F_2(\vec{x}) = x_j$ and $F_1(\vec{x}) = x_i$, by the symmetric version of Lemma~\ref{l:non-separated-inside}, because $\r_p(j, x_j) =\,\downarrow$. Therefore, $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$.
\end{itemize}

As for instances $\vec{x}$ with $x_k < x_i$, we first show that either $\l(k, b) = (j, b)$ or $\l_p(k, b) =\,\uparrow$, for all locations $b$ (i.e., we exclude the possibility that for some $b$, $\l(k, b) = (i, b)$). %In the former case, the facilities are allocated similarly to the case where $x_i < x_k$. In the latter case, the facilities are allocated to the two extremes.

%In Case II, where there is an agent-location pair $(i, a)$ with $\l_p(i, a) = a$, we have also to determine the facility allocation for instances $\vec{x}$ where $x_k < x_i$. To this end, we first show that either $\l(k, b) = (j, b)$ or $\l_p(k, b) =\,\uparrow$, for all locations $b$ (i.e., we exclude the possibility that for some location $b$, $\l(k, b) = (i, b)$).

To reach a contradiction, let us assume that for some location $b$, $\l(k, b) = (i, b)$. Let $\vec{y}$ be any $(k,i|j)$-well-separated instance with $y_k = b$. Since $\l(k, b) = (i, b)$, since $k$ is the leftmost agent in $\vec{y}$, and since $y_i > b$, Lemma~\ref{l:non-separated} implies that $y_i \in F(\vec{y})$.
%
Moreover, since $\r(j, y_j) =\,\downarrow$, and since $j$ is the rightmost and $y_k$ is the leftmost agent in $\vec{y}$, the symmetric version of Lemma~\ref{l:non-separated-inside} implies that $y_k \in F(\vec{y})$. Therefore, the agent $j$ is served by the facility at $y_i$, which contradicts $F$'s bounded approximation ratio, because $\vec{y}$ is an $(k,i|j)$-well-separated instance.

To conclude the proof, we distinguish between the case where there is a location $b$ such that $\l(k, b) = (j, b)$, and the case where for all locations $b$, $\l_p(k, b) =\,\uparrow$.
%
In the former case, the facilities are allocated similarly to the case where $x_i < x_k$, while in the latter case, the facilities are allocated to the two extremes.
%
%We recall that $\l_p(j, b) =\,\uparrow$ and $\r_p(j, b) =\,\downarrow$, for all locations $b$, by Lemma~\ref{l:only-dictator}, because $\l(i, a) = (j, a)$.

If there is a location $b$ such that $\l(k, b) = (j, b)$, then for all locations $b' \in \reals$, $\l(k, b') = (j, b')$, by Lemma~\ref{l:always-a}, and $\r(i, b') = (j, b')$, by Lemma~\ref{l:others-a}. Therefore, for all instances $\vec{x}$ with $x_k < x_i$, $x_j \in F(\vec{x})$. More specifically, if $x_k < x_j$, this follows from Lemma~\ref{l:non-separated}, while if $x_j < x_i$, this follows from the symmetric version of Lemma~\ref{l:non-separated}. Then, % as before,
we use Lemma~\ref{l:non-separated-inside}, and obtain the conclusion of the lemma for all instances $\vec{x}$ with $x_k < x_i$\,:

\begin{itemize}
\item For all instances $\vec{x}$ with $x_k < x_j < x_i$, $x_j \in F(\vec{x})$.

\item For all instances $\vec{x}$ with $x_j < x_k < x_i$, $F_1(\vec{x}) = x_j$ and $F_2(\vec{x}) = x_i$, by Lemma~\ref{l:non-separated-inside}, because $\l_p(j, x_j) =\,\uparrow$. Therefore, $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$.

\item For all instances $\vec{x}$ with $x_k < x_i < x_j$, $F_2(\vec{x}) = x_j$ and $F_1(\vec{x}) = x_k$, by the symmetric version of Lemma~\ref{l:non-separated-inside}, because $\r_p(j, x_j) =\,\downarrow$. Therefore, $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$.
\end{itemize}


Otherwise, for all locations $b$, $\l_p(k, b) =\,\uparrow$. We observe that for all locations $b$, $\r_p(i, b) =\,\downarrow$. Otherwise, there would exist a location $b'$ with $\r_p(i, b') = b'$, by Lemma~\ref{l:i-cases}, and thus $\l_p(k, b') = b'$, by Lemma~\ref{l:others-a}, a contradiction.
%
As before, we now use Lemma~\ref{l:non-separated-inside}, and obtain the conclusion of the lemma for all instances $\vec{x}$ with $x_k < x_i$. More specifically, since $x_k < x_i$, the leftmost agent of $\vec{x}$ is either $k$ or $j$. If the leftmost agent is $k$ (resp. $j$), $F_2(\vec{x}) = \max\vec{x}$, by Lemma~\ref{l:non-separated-inside}, because $\l_p(k, x_k) =\,\uparrow$ (resp. $\l_p(j, x_j) =\,\uparrow$).
%
Similarly, the rightmost agent of $\vec{x}$ is either $j$ or $i$. If the rightmost agent is $j$ (resp. $i$), $F_1(\vec{x}) = \min\vec{x}$, by the symmetric version of Lemma~\ref{l:non-separated-inside}, because $\r_p(j, x_j) =\,\downarrow$ (resp.
$\r_p(i, x_i) =\,\downarrow$).
%
%Again, we use Lemma~\ref{l:non-separated-inside}, and obtain the conclusion of the lemma for all instances $\vec{x}$ with $x_k < x_i$\,:
%
%\begin{itemize}
%\item For all instances $\vec{x}$ with $x_j < x_k < x_i$, $F_1(\vec{x}) = x_j$, by the symmetric version of Lemma~\ref{l:non-separated-inside}, because $\r_p(i, x_i) =\,\downarrow$, and $F_2(\vec{x}) = x_i$, by Lemma~\ref{l:non-separated-inside}, because $\l_p(j, x_j) =\,\uparrow$.
%
%\item For all instances $\vec{x}$ with $x_k < x_j < x_i$, $F_1(\vec{x}) = x_k$, by the symmetric version of Lemma~\ref{l:non-separated-inside}, because $\r_p(i, x_i) =\,\downarrow$, and $F_2(\vec{x}) = x_i$, by Lemma~\ref{l:non-separated-inside}, because $\l_p(k, x_k) =\,\uparrow$.
%
%\item For all instances $\vec{x}$ with $x_k < x_i < x_j$, $F_1(\vec{x}) = x_k$, by the symmetric version of Lemma~\ref{l:non-separated-inside}, because $\r_p(j, x_j) =\,\downarrow$, and $F_2(\vec{x}) = x_j$, by Lemma~\ref{l:non-separated-inside}, because $\l_p(k, x_k) =\,\uparrow$.
%\end{itemize}
%
Thus, if $\l_p(k, b) =\,\uparrow$, for all instances $\vec{x}$ with $x_k < x_i$, $F(\vec{x}) = (\min\vec{x}, \max\vec{x})$.
\qed\end{proof}


